#include <iostream>
#include <string>
#include "queue.h"
#include "stack.h"

using namespace std;

/**
 *  算法分析：输入一个字符串存入队列中，因为回文需要比较头尾，
 *  而队列先进先出，无法比较头尾，因而需要借助栈的先进后出特性，
 *  找到队尾的元素。然后和队头的元素进行比较。
 *
 */
bool isHuiWen(Queue Q){
    int l= Q.getSize();
    int n = l/2;
    int isOdds = l&1;  //判断是否奇数
    int i =0;
    bool flag = true;

    Stack * stack_2;
    stack_2 = new Stack(n);
    while(i<n){
        stack_2->push(Q.pop());  //取出队列的元素
        i++;
    }
    if(isOdds){
        Q.pop();  //弹出多余的元素
    }
    i =0;
    while(i<n){
        if(Q.pop() != stack_2->pop()){   //取出栈顶元素和队头元素比较
            flag = false;
        }
        i++;
    }

    return flag;

}

main (){
    char a;
    bool result;
    Queue *queue_1;

    cout <<"请输入字符，以#结束输入:\n";

    queue_1 = new Queue(5); //暂定5个元素，如果不够，队列可以自行扩展
    while(cin.get(a) && a !='#'){
        if(a=='\n') continue;  //过滤误输入的换行符
        queue_1->push(a);
    }
    queue_1->output();

    //判断是否是回文
   result =isHuiWen(*queue_1); 
   if(result){
       cout << "是回文.";
   }else{
       cout <<"不是回文";
   }
    
}
